package style.Leetcode.初级算法.tree.tree_20220827_1_验证二叉搜索树;

import style.Leetcode.初级算法.tree.TreeNode;

/**
 * 验证二叉搜索树
 *  给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 *
 * 有效 二叉搜索树定义如下：
     * 节点的左子树只包含 小于 当前节点的数。
     * 节点的右子树只包含 大于 当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
 *  输入：root = [2,1,3]
 * 输出：true
 *
 * 输入：root = [5,1,4,null,null,3,6]
 * 输出：false
 * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
 */
public class Solution {
    /**
     * 递归算法
     */
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        if (root == null) return true;
        // 每个节点如果超过这个范围，直接返回false
        if (root.val >= maxVal || root.val <= minVal) {
            return false;
        }
        return isValidBST(root.left, minVal, root.val)
                && isValidBST(root.right, root.val, maxVal);
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(4);
        treeNode.left = new TreeNode(3);
        treeNode.left.left = null;
        treeNode.left.right = null;
        treeNode.right = new TreeNode(20);
        treeNode.right.left = new TreeNode(5);
        treeNode.right.left.left = null;
        treeNode.right.left.right = null;
        treeNode.right.right = new TreeNode(30);
        treeNode.right.right.left = null;
        treeNode.right.right.right = null;
        Solution solution = new Solution();
        System.out.println(solution.isValidBST(treeNode));
    }


}
